|
Interval edge coloring is a type of edge coloring in which edges are colored such that they form a set of intervals and each color in the interval set is at least used once to color the edges of the graph.It is to be noted that at each vertex in the graph the colors used form a consecutive set of natural numbers. ==History== The concept of consecutive edge-coloring was introduced with the terminology 'interval edge coloring' by Asratian and Kamalian in 1987 in their paper "Interval colorings of edges of a multigraph". Since interval edge coloring of graphs was introduced mathematicians have been investigating the existence of interval edge colorable graphs as not all graphs allow interval edge coloring. A simple family of graphs that allows interval edge coloring is complete graph of even order and a counter example of family of graphs includes complete graphs of odd order. The smallest graph that doesnot allow interval colorability.There are even graphs discovered with 28 vertices and maximum degree 21 that is not interval colorable by Sevast’janov though the interval colorability of graphs with maxium degree lying between four and twelve is still unknown. Astrain and Kamalian in their paper〔 proved that if a graph is interval colorable then the edge chromatic number is les than or equal to one les than it's number of vertices and also noted that if G is r-regular, then G has an interval coloring if and only if G has a proper r-edge-coloring. Interval edge coloring is investigated in regular graphs.bipartite graphs which are regular and not regular,planar graphs,among the other extensions that has been initiated in interval edge coloring. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Interval edge coloring」の詳細全文を読む スポンサード リンク
|